package algorithm.beforestart.primary.linkList;

import java.util.List;
import java.util.Stack;

public class reverseList {

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        if (head.next == null) {
            return head;
        }
        ListNode next = head.next;
        if (next.next == null) {
            next.next = head;
            head.next = null;
            return next;
        }
        ListNode node = reverseList(next);

        ListNode newhead = node;
        while (node.next != null) {
            node = node.next;
        }
        node.next = head;
        head.next = null;
        return newhead;

    }

    public static ListNode reverseList2(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        if (head == null) {
            return null;
        }
        stack.add(head);
        while (head.next != null) {
            ListNode node = head.next;
            stack.add(node);
            head = node;
        }
        ListNode first = stack.pop();
        ListNode temp = first;
        while (!stack.isEmpty()) {
            temp.next=stack.pop();
            temp = temp.next;

        }
        temp.next = null;
        return first;

    }


    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);

//        System.out.println();
       ListNode listNodeback= reverseList2(node);

        print(listNodeback);

    }

    private static void print(ListNode node) {
        System.out.println(node.val);
        while (node.next != null) {
            node = node.next;
            System.out.println(node.val);
        }
    }
}
